React diff揭秘
React 框架内部的运作可以分为 3 层：
- Virtual DOM 层，描述页面长什么样。
- Reconciler 层，负责调用组件生命周期方法，进行 Diff 运算等。
- Renderer 层，根据不同的平台，渲染出相应的页面，比较常见的是 ReactDOM 和 ReactNative。
ReactChildFiber.new.js中
Diff的入口函数
1 | // 根据newChild类型选择不同diff函数处理 |
newChild参数就是本次更新的 JSX 对象（对应ClassComponent的this.render方法返回值，或者FunctionComponent执行的返回值）
同级的节点数量将Diff分为两类：
- 当newChild类型为
object、number、string，代表同级只有一个节点 - 当newChild类型为
Array时，代表同级有多个节点
情况一：同级只有一个节点
对于单个节点，我们以类型object为例，会进入reconcileSingleElement
1 | const isObject = typeof newChild === 'object' && newChild !== null; |
Fiber 其实指的是一种数据结构，它可以用一个纯 JS 对象来表示：
1 | const fiber = { |
在render阶段会生成的Fiber结构
Fiber中可以保存节点的类型，例子中App节点是一个函数组件节点，div节点是一个原生DOM节点，I am节点是一个文本节点。
可以保存节点的信息（比如state，props）。
可以保存节点对应的值（比如App节点对应App函数，div节点对应div DOMElement）。这样的结构也解释了为什么函数组件通过Hooks可以保存state。因为state并不是保存在函数上，而是保存在函数组件对应的Fiber节点上。
可以保存节点的行为（更新/删除/插入）
div Fiber.return = App Fiber; 即用return指向自己的父节点。父级叫return不叫parent
判断DOM节点是否可以复用，让我们通过代码看看是如何判断的：
1 | function reconcileSingleElement( |
从代码可以看出，React通过先判断key是否相同，如果key相同则判断type是否相同，只有都相同时一个DOM节点才能复用。
练习题
请判断如下JSX对象对应的DOM元素是否可以复用：
1 | // 习题1 更新前 |
`
`
`
`
`
`
`
习题1: 未设置key prop默认 key = null;，所以更新前后key相同，都为null，但是更新前type为div，更新后为p，type改变则不能复用。
习题2: 更新前后key改变，不需要再判断type，不能复用。
习题3: 更新前后key改变，不需要再判断type，不能复用。
习题4: 更新前后key与type都未改变，可以复用。children变化，DOM的子元素需要更新。
情况二：同级有多个元素的Diff
刚才我们介绍了单一元素的Diff，现在考虑我们有一个FunctionComponent：
1 | function List () { |
返回值JSX对象的children属性不是单一元素，而是包含四个对象的数组
在这种情况下，reconcileChildFibers的newChild参数为Array，就执行到了这儿
来看看React如何处理同级多个元素的Diff。
同级多个节点详解
节点更新
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// 情况1 节点更新
// 之前
<ul>
<li key="0" className="before">0<li>
<li key="1">1<li>
</ul>
// 之后情况1 节点属性变化
<ul>
<li key="0" className="after">0<li>
<li key="1">1<li>
</ul>
// 之后情况2 节点类型更新
<ul>
<div key="0">0<li>
<li key="1">1<li>
</ul>
节点新增或减少
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// 情况2 节点新增或减少
// 之前
<ul>
<li key="0">0<li>
<li key="1">1<li>
</ul>
// 之后情况1 新增节点
<ul>
<li key="0">0<li>
<li key="1">1<li>
<li key="2">2<li>
</ul>
// 之后情况2 删除节点
<ul>
<li key="1">1<li>
</ul>
节点位置变化
1
2
3
4
5
6
7
8
9
10
11
12
13// 情况3 节点位置变化
// 之前
<ul>
<li key="0">0<li>
<li key="1">1<li>
</ul>
// 之后
<ul>
<li key="1">1<li>
<li key="0">0<li>
</ul>
同一次同级多个元素的Diff，一定属于以上三种情况中的一种或多种。
该如何设计算法呢
首先想到的是方案是：
- 判断当前节点的更新属于哪种情况
- 如果是新增，执行新增逻辑
- 如果是删除，执行删除逻辑
- 如果是更新，执行更新逻辑
按这个方案，其实有个隐含的前提，上述不同操作的优先级是相同的
但React团队发现，在日常开发中，相对于增加和删除，更新组件发生的频率更高。所以React Diff会优先判断当前节点是否属于更新。
虽然本次更新的JSX对象newChildren为数组形式，但是和newChildren中每个值进行比较的是上次更新的Fiber节点，Fiber节点的同级节点是由sibling（兄弟节点）指针链接形成的链表。
即 newChildren[0]与oldFiber比较，newChildren[1]与oldFiber.sibling比较。
单链表无法使用双指针，所以无法对算法使用双指针优化。
基于以上原因，Diff算法的整体逻辑会经历两轮遍历。
第一轮遍历：处理更新的节点。
第二轮遍历：处理剩下的不属于更新的节点。
第一遍遍历
- 遍历newChildren，i = 0，将newChildren[i]与oldFiber比较，判断DOM节点是否可复用。
- 如果可复用，i++，比较newChildren[i]与oldFiber.sibling是否可复用。可以复用则重复步骤2。
- 如果不可复用，立即跳出整个遍历。
- 如果newChildren遍历完或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历。
当最终完成遍历后，会有两种结果：
结果一：如果是步骤3跳出的遍历，newChildren没有遍历完，oldFiber也没有遍历完。
举个栗子🌰
如下代码中，前2个节点可复用，key === 2的节点type改变，不可复用，跳出遍历。
此时oldFiber剩下key === 2未遍历，newChildren剩下key === 2、key === 3未遍历。
1 | // 之前 |
结果二：如果是步骤4跳出的遍历，可能newChildren遍历完，或oldFiber遍历完，或他们同时遍历完。
再来个🌰
1 | // 之前 |
第二轮遍历
对于结果二，聪明的你想一想🐯，newChildren没遍历完，oldFiber遍历完意味着什么？
老的DOM节点都复用了，这时还有新加入的节点，意味着本次更新有新节点插入，我们只需要遍历剩下的newChildren依次执行插入操作（Fiber.effectTag = Placement;）。
effectTag字段表示当前Fiber需要执行的副作用，最常见的副作用是：
- Placement 插入DOM节点
- Update 更新DOM节点
- Deletion 删除DOM节点
同样的，我们举一反三。newChildren遍历完，oldFiber没遍历完意味着什么？
意味着多余的oldFiber在这次更新中已经不存在了，所以需要遍历剩下的oldFiber，依次执行删除操作（Fiber.effectTag = Deletion;）。
那么结果一怎么处理呢？newChildren与oldFiber都没遍历完，这意味着有节点在这次更新中改变了位置。
接下来，就是Diff算法最精髓的部分！！！
处理位置交换的节点
为了快速的找到key对应的oldFiber，我们将所有还没处理的oldFiber放进以key属性为key，Fiber为value的map。
1 | const existingChildren = mapRemainingChildren(returnFiber, oldFiber); |
源码部分1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function mapRemainingChildren(
returnFiber: Fiber,
currentFirstChild: Fiber,
): Map<string | number, Fiber> {
// Add the remaining children to a temporary map so that we can find them by
// keys quickly. Implicit (null) keys get added to this set with their index
// instead.
const existingChildren: Map<string | number, Fiber> = new Map();
let existingChild = currentFirstChild;
while (existingChild !== null) {
if (existingChild.key !== null) {
existingChildren.set(existingChild.key, existingChild);
} else {
existingChildren.set(existingChild.index, existingChild);
}
existingChild = existingChild.sibling;
}
return existingChildren;
}
再遍历剩余的newChildren，通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber。
接下来是重点哦，敲黑板 👨🏫
在我们第一轮和第二轮遍历中，我们遇到的每一个可以复用的节点，一定存在一个代表上一次更新时该节点状态的oldFiber，并且页面上有一个DOM元素与其对应。
那么我们在Diff函数的入口处，定义一个变量
上篇React diff 中的LastIndex
1 | let lastPlacedIndex = 0; |
该变量表示当前最后一个可复用的节点，对应的oldFiber在上次更新中的所在的位置索引，我们通过这个变量判断节点是否需要移动。
这里我们简化一下书写，每个字母代表一个节点，字母的值代表节点的key
// 之前
abcd
// 之后
acdb
| index | 节点 | oldIndex | lastIndex | 操作 |
|---|---|---|---|---|
| 0 | B | 0 | 0 | oldIndex(0)==lastIndex(0),不动 |
| 1 | c | 2 | 2 | oldIndex(2)==lastIndex(2),不动 |
| 2 | d | 3 | 3 | oldIndex(3)==lastIndex3),不动 |
| 3 | b | 1 | 3 | oldIndex(1)<lastIndex(3),节点b移动至index(3)的位置 |
1 | // 之前 |
相信你已经明白了节点移动是如何判断的
再来看一个例子
1 | // 之前abcd |
1 | ===第一轮遍历开始=== |
可以看到，我们以为从 abcd 变为 dabc，只需要将d移动到前面。
但实际上React保持d不变，将abc分别移动到了d的后面。
从这点可以看出，考虑性能，我们要尽量减少将节点从后面移动到前面的操作。
注释过的React源码
1 | // diff算法会进行两轮遍历，可能中间有中断，时间复杂度O(n) |
